package 算法练习;/**
 * @author： li
 * @date： 2022-01-29 13:37
 * @version 1.0
 */

/*问题描述
　　斐波那契串由下列规则生成：
　　F[0] = "0";
　　F[1] = "1";
　　F[n] = F[n-1] + F[n-2] （n≥2，+表示连接）
　　给出一个由0和1构成的串S和一个数n，求出F[n]中S出现的次数。
输入格式
　　第一行一个数n。
　　第二行一个01串S。
输出格式
　　答案。
样例输入
96
10110101101101
样例输出
7540113804746346428
数据规模和约定
　　n≤2^63-1，子串长≤10000，答案≤2^63-1。
 */
import java.util.Scanner;

public class 斐波那契数串_递推{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong();
        String m=sc.next();
        int i=0;
        for(;i<n;i++) {
            long sum=swap(i,m);
            //如果字符串str存在于指定字符串m中，打破循环，使用斐波那契数列规律求出
            if(sum==1) {
                break;
            }
        }
        //从i开始，因为斐波拉契数列的定义F(n)=F(n-1)+F(n-2)，以后的斐波拉契一定回有这个
        long su=adds(i-1,n);//（i-1）是因为for循环之后，i++了
        System.out.println(su);
    }
    //继续菲波那切数列规律进行计算
    public static long adds(long m,long n) {
        long a=0;
        long b=1;
        for(long j=m;j<=n;j++) {
            long t=b;
            b=b+a;
//            System.out.println(b);
            a=t;
        }
        return b-1;
    }
    //获取第一次出现子串的时候
    public static long swap(long m,String s) {
        String pre="0";
        String cur="1";
        for(int j=2;j<=m;j++) {
            String t=cur;
            cur=pre+cur;
            pre=t;
        }
        //计算字串个数
        long sum=0;
        for(int i=0;i<cur.length()-s.length();i++) {
            String str=cur.substring(i,i+s.length());
            if(str.equals(s)) {
                return 1;
            }
        }
        return sum;
    }
}
